package com.suanfa.node;

public class MergeKSortNodeList {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(6);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        listNode5.next = listNode6;

        ListNode listNode11 = new ListNode(1);
        ListNode listNode12 = new ListNode(2);
        ListNode listNode13 = new ListNode(3);
        ListNode listNode14 = new ListNode(4);
        ListNode listNode15 = new ListNode(5);
        ListNode listNode16 = new ListNode(6);
        listNode11.next = listNode12;
        listNode12.next = listNode13;
        listNode13.next = listNode14;
        listNode14.next = listNode15;
        listNode15.next = listNode16;

        ListNode node = merge(listNode1, listNode11);
        while(node != null){
            System.out.println(node.value);
            node = node.next;
        }
    }



    public static ListNode merge(ListNode list1, ListNode list2){
        ListNode temp = new ListNode(Integer.MIN_VALUE);
        temp.next = list1;
        ListNode p1 = list1;
        ListNode p2 = list2;
        ListNode current = temp;

        while (p1 != null || p2 != null){
            if(p1 == null){
                current.next = p2;
                break;
            }
            if(p2 == null){
                current.next = p1;
                break;
            }
            if(p2.value <= p1.value){
                current.next = p2;
                p2 = p2.next;
            }else {
                current.next = p1;
                p1 = p1.next;
            }
            current = current.next;
        }
        return temp.next;
    }
}
